package Cache;

import java.util.HashMap;
import java.util.Hashtable;
import java.util.LinkedHashMap;


@SuppressWarnings("all")
/**
 * 实现一个LRU缓存算法策略
 */


/**
 * 定义双向链表类
 * 双向链表中实现对节点数据的保存，一共有一下的三种情况：
 *      1. 正常添加
 *      2. 链表满 (按照特定规则删除节点之后在将新的节点添加到链表中)
 *      3. 添加的是重复的key (覆盖原来的key对应的value)
 */
class DoubleLinkedList {

}

/**
 * 基于双向链表 + HashMap实现 LRU缓存淘汰算法机制
 *
 * 分析LRU缓存淘汰机制的实现历程：
 *      首先我们先考虑到底什么是LRU算法? 所谓的LRU全程为 Least Recently Used，最近最少使用算法
 *      我们从具体的例子来看，对于LRU这个算法，对于大多数需要缓存的结构都需要的，下面我们从数据库这
 *      个角度来看LRU，redis是一款实现缓存的常用框架。一般而言，如果想将数据从数据库获取到页面上展
 *      示，一般而言都需要通过DB，但是对于DB而言，其消耗比较大，对于高并发量的访问容易造成服务延迟，
 *      甚至导致DB宕机，如果加入缓存机制，首先我们需要当前数据在页面上显示，此时我们先从缓存中查询，
 *      如果缓存中没有该数据，就从DB中取出数据，然后将该数据先存到缓存中，然后再返回该数据到页面上。
 *      下次如果我们想要使用该数据，直接从缓存中获取即可，不但减轻了DB的压力，而且响应速度也得到了提
 *      升。那么问题随之而来，由于DB的大小一般远大于缓存，假设DB的容量可以存放100W+的数据，而缓存只
 *      能存放1w条数据，显然如果按照上述的方式放置到缓存中，缓存并没有这么大的容量来存放，所以我们需要
 *      淘汰掉一部分缓存来存放新的数据，如果淘汰了，这就是LRU的作用
 *
 *      如何实现LRU呢? 对于LRU的实现无非就是数据结构+算法，对于缓存而言，效率是非常重要的，如何如果每次
 *      需要遍历结构才能找到最近最少使用的，显然这个效率对于数据量较大的时候是不好的，下面从几种结构来分析
 *      优化LRU的实现
 *
 *      LRU的主要操作就两个：get操作和put操作，get操作是获取缓存中的数据，put操作是添加数据到缓存中
 *
 *      1. 采用数组实现LRU
 *
 *      2. 采用链表实现LRU
 *
 *      3. 采用链表+HashMap实现LRU
 *
 *      4. 采用双向链表+HashMap实现LRU(其两个操作的时间复杂度最低O(1))
 *
 */
@SuppressWarnings("all")
public class LRUCache {

    class DLinkedNode {
        int key;
        int value;
        DLinkedNode pre;
        DLinkedNode post;
    }

    private Hashtable<Integer, DLinkedNode>
            cache = new Hashtable<Integer, DLinkedNode>();
    private int count;
    private int capacity;
    private DLinkedNode head, tail;

    public LRUCache(int capacity) {
        this.count = 0;
        this.capacity = capacity;

        head = new DLinkedNode();
        head.pre = null;

        tail = new DLinkedNode();
        tail.post = null;

        head.post = tail;
        tail.pre = head;
    }

    public int get(int key) {

        DLinkedNode node = cache.get(key);
        if(node == null){
            return -1; // should raise exception here.
        }

        // move the accessed node to the head;
        this.moveToHead(node);

        return node.value;
    }


    public void set(int key, int value) {
        DLinkedNode node = cache.get(key);

        if(node == null){

            DLinkedNode newNode = new DLinkedNode();
            newNode.key = key;
            newNode.value = value;

            this.cache.put(key, newNode);
            this.addNode(newNode);

            ++count;

            if(count > capacity){
                // pop the tail
                DLinkedNode tail = this.popTail();
                this.cache.remove(tail.key);
                --count;
            }
        }else{
            // update the value.
            node.value = value;
            this.moveToHead(node);
        }
    }
    /**
     * Always add the new node right after head;
     */
    private void addNode(DLinkedNode node){
        node.pre = head;
        node.post = head.post;

        head.post.pre = node;
        head.post = node;
    }

    /**
     * Remove an existing node from the linked list.
     */
    private void removeNode(DLinkedNode node){
        DLinkedNode pre = node.pre;
        DLinkedNode post = node.post;

        pre.post = post;
        post.pre = pre;
    }

    /**
     * Move certain node in between to the head.
     */
    private void moveToHead(DLinkedNode node){
        this.removeNode(node);
        this.addNode(node);
    }

    // pop the current tail.
    private DLinkedNode popTail(){
        DLinkedNode res = tail.pre;
        this.removeNode(res);
        return res;
    }
}